1. Field of Invention
The present invention relates to a secure encryption method, and more particularly to a method for converting a class of abstract computation machines (state machines) to a polynomial representation.
2. Background of the Invention
Previous work on encrypted functions is described in T. Sander and C. Tschudin, “Protecting Mobile Agents Against Malicious Hosts,” Springer LNCS 1419, pp. 44–60 (hereinafter “Sander”) (the contents of which are incorporated herein by reference), which describes a system for evaluating a single encrypted polynomial. Sander describes encrypting polynomials by selecting an appropriate algorithm for encryption of the polynomial's coefficients on an individual basis.
Additional research was performed on privacy homomorphisms. A simplistic description of a privacy homomorphism is an encryption function, e, such thate(x+y)=e(x)+e(y), e(xy)=e(x)e(y), etc.Such privacy homomorphisms are discussed in R. Rivest, L. Adleman, and M. Dertouzos, “On Data Banks and Privacy Homomorphisms,” in “Foundations of Secure Computation,” editor R. DeMillo, Academic Press, 1978, ISBN 0-12-210350-5 (hereinafter “Rivest”), the contents of which are incorporated herein by reference.
Multi-party computations are also known. Common for many of these protocols is that they solve the problem where m people wish to evaluate a function ƒ(x1, . . . , xm), where each person Pi knows only xi, such that:                1. no information or a minimum of information about any xj for j≠i is leaked to Pi during the evaluation of the function ƒ        2. the identity of all cheaters is known by the time the evaluation is completed        3. the value of ƒ(x1, . . . , xm) becomes known to all participants simultaneously (or almost simultaneously) upon termination of the protocol.One of the first protocols for secure multiparty computations was proposed in A. Yao, “Protocols for Secure Computations (extended abstract)”, 23rd Annual Symposium on Foundations of Computer Science, 1982, IEEE Computer Society's Technical Committee on Mathematical Foundations of Computing (hereinafter “Yao”), the contents of which are incorporated herein by reference. Yao describes the case where m people want to compute ƒ(x1, . . . , xm) under the following conditions:        1. each person Pi initially knows only xi, and does not the value of any xj for j≠i        2. ƒ must be computed such that after the computation, person Pi still knows the exact value of only xi, and does not the value of any xj for j≠iYao describes computing functions of the form ƒ: X1× . . . ×Xm→V.        
Another approach is described in G. Brassard and C. Crepeau, “Zero-Knowledge Simulation of Boolean Circuits,” Advances in Cryptology—CRYPTO'86: Proceedings, Lecture Notes in Computer Science, Vol. 263, pp. 223–233, Springer-Verlag, 1986 (hereinafter “Brassard”), the contents of which are incorporated herein by reference. Brassard describes a method of simulating boolean circuits using zero-knowledge interactive protocols. For example, person B computes a function ƒ:D→{0,1} in several rounds with the aid of person A. Person A provides data about the evaluation to person B using a zero-knowledge interactive protocol. Person B cannot compute the encrypted evaluation from encrypted data supplied by person A.
Chaum, Damgård, and van de Graaf, “Multiparty Computations Ensuring Privacy of Each Party's Input and Correctness of the Result,” Advances in Cryptology—CRYPTO'87: Proceedings, editor C. Pomerance, Lecture Notes in Computer Science, Vol. 293, pp. 87–119, Springer-Verlag, 1987 (hereinafter “Chaum”) (the contents of which are incorporated herein by reference) describes an alternative to Yao's protocols. That alternative requires less computation, but assumes quadratic residues.
Abadi, Feigenbaum, and Kilian, “On Hiding Information from an Oracle,” Journal Computer System Science, Vol. 39 (1989), 21–50 (hereinafter “Abadi—1”) (the contents of which are incorporated herein by reference) discusses computing with encrypted data. The abstract describes that: Player A wishes to know the value ƒ(x) for some x but lacks the power to compute it. Player B has the power to compute f and is willing to send ƒ(y) to A if she sends him y, for any y. A encrypts x, sends y=E(x) to B, who then computes ƒ(y), returns this result to A, who then infers ƒ(x) from ƒ(y). M. Abadi and J. Feigenbaum, “Secure Circuit Evaluation,” Journal of Cryptology, No. 2, pp. 1–12, 1990 (hereinafter “Abadi—2”) (the contents of which are incorporated herein by reference) describes a related problem. A protocol is used to evaluate a function ƒ(x) by two parties, where one knows how to compute ƒ but does not know x, and the other party knows x, but not how to compute ƒ. The ƒ in question would be expressed as a boolean circuit. This is in fact again the privacy homomorpism problem.
Additional work has been performed recently by M. Naor and B. Pinkas, “Oblivious Transfer and Polynomial Evaluation”, STOC'99, pp.245–254, and C. Cachin, J. Camenisch, J. Kilian, and J. Mueller, “One-Round Secure Computation and Secure Autonomous Mobile Agents”, ICALP 2000, pp.512–523, and D. Beaver, “Minimal-Latency Secure Function Evaluation”, EUROCRYPT 2000, pp.335–350 (the contents of each of those references is incorporated herein by reference).
Encryption systems are discussed in patents such as: U.S. Pat. No. 4,120,030, U.S. Pat. No. 4,168,396, U.S. Pat. No. 4,278,837, U.S. Pat. No. 4,306,389, U.S. Pat. No. 4,319,079, U.S. Pat. No. 4,433,207, U.S. Pat. No. 4,465,901, U.S. Pat. No. 4,633,388, U.S. Pat. No. 4,764,959, U.S. Pat. No. 4,847,902, U.S. Pat. No. 4,937,861, U.S. Pat. No. 5,007,082, U.S. Pat. No. 5,033,084, U.S. Pat. No. 5,153,921, U.S. Pat. No. 5,341,429, U.S. Pat. No. 5,392,351, U.S. Pat. No. 5,544,244, U.S. Pat. No. 5,592,549, U.S. Pat. No. 5,892,899, U.S. Pat. No. 6,052,870, and U.S. Pat. No. 6,049,609.
As additional background, a brief discussion of representing programs as polynomials is provided herein. The polynomial representation of a program is generated in two steps. First, the program as represented in a programming language is transformed to an abstract computation machine. Second, the abstract computation machine is transformed to a polynomial mapping. As would be appreciated by one of ordinary skill in the art, the transformation of a program in a programming language is a process specific to the selected programming language, and transformation methods are constructed for each programming language.
L. Blum, M. Shub, and S. Smale, “On a Theory of Computation and Complexity over the Real Numbers: NP-completeness, Recursive Functions, and Universal Machines,” Bulletin of the American Mathematical Society, vol. 21, No. 1, pp. 1–46 (hereinafter “Blum”) (the contents of which are incorporated herein by reference) describes transforming abstract computation machines to polynomials. In addition, it is possible to represent the computations of most types of finite automata using polynomials over a finite field.